package m202405.d12;

import java.util.HashMap;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/13 11:39
 */
public class Q146 {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(2, 1);
        lruCache.put(2, 2);
        lruCache.get(2);
        lruCache.put(3, 3);
//        lruCache.get(2);
//        lruCache.put(4, 4);
//        lruCache.get(1);
//        lruCache.get(3);
//        lruCache.get(4);
    }

    public static class LRUCache {
        Map<Integer, Node> map;
        int capacity;
        Node head;
        Node tail;

        public LRUCache(int capacity) {
            this.map = new HashMap<>();
            this.capacity = capacity;
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            removeNode(node);
            addNode(node);
            return node.val;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.remove(key);
                removeNode(node);
                node.val = value;
                addNode(node);
                map.put(key, node);
                return;
            }
            Node node = new Node(key, value);
            map.put(key, node);
            addNode(node);
            if (map.size() > capacity) {
                map.remove(tail.pre.key);
                removeNode(tail.pre);
            }
        }

        private void removeNode(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.next = null;
            node.pre = null;
        }

        private void addNode(Node node) {
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }

        private static class Node {
            int key;
            int val;
            Node pre;
            Node next;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }
    }
}
